package com.iceph0x.algorithm.sort;

import java.util.Comparator;

import com.iceph0x.algorithm.framework.ISort;

public class HeapSort implements ISort {

    @Override
    public void sort(int[] data) {
        if (data == null || data.length < 2)
            return;

        setupHeap(data);
        for (int i = data.length - 1; i > 0; --i) {
            swap(data, 0, i);
            adjustSubHeap(data, 0, i);
        }
    }

    /**
     * set up small root heap
     * 
     * @param data
     */
    private void setupHeap(int[] data) {
        int size = data.length;
        for (int i = (size - 1) >> 1; i >= 0; --i) {
            adjustSubHeap(data, i, size);
        }
    }
    
    private void adjustSubHeap(int[] data, int i, int size) {
        int child;
        int childIndex = (i << 1) + 1;
        while (childIndex < size) {
            child = data[childIndex];
            if (childIndex + 1 < size && data[childIndex + 1] < child) {
                ++ childIndex;
                child = data[childIndex];
            }
            
            if (data[i] > child) {
                data[childIndex] = data[i];
                data[i] = child;
            }
            else {
                break;
            }
            i = childIndex;
            childIndex = (i << 1) + 1;
        }
    }
    
    private void swap(int[] data, int i, int j) {
        if (data[i] == data[j])
            return;
        
        data[i] ^= data[j];
        data[j] ^= data[i];
        data[i] ^= data[j];
    }
    
    @Override
    public void sort(Object[] data, Comparator<Object> c) {
        // TODO Auto-generated method stub
        
    }
}
